The invention concerns the structure and operation of threshold logic circuits which implement the COMPARE and ADD functions.
Specialized circuits which count inputs and provide output signals indicating the relationship of the count with a predetermined threshold are known in the art. These elements are called "threshold gates". Conventionally, a threshold gate produces a binary signal (a "bit") conditioned to a first state if the sum of weighted input bits is equal to or greater than a certain value (the "threshold value"). The threshold gate conditions its output bit to the other binary value when the sum of weighted input bits is less than the threshold value.
The art recognizes a particular class of threshold gates in which a gate conditions its output according to the binary value assumed by the majority of bits input to the gate. Such gates are called "majority gates". It is known to use majority gates in order to combine variables and to sum the variables in such a manner that the summation is described by a polynomial whose terms are given by Boolean variables. In these constructions, a first level of gates receives various combinations of variables, combines them, and provides outputs representing the combinations. Following levels combine these outputs in prescribed ways, generate other outputs, and so on, until, at a last level, all outputs of the preceding level are collected by a majority gate whose output is conditioned according the function it implements. When plural level majority gate circuits are constructed to compute polynomials, the output of the last gate is referred to as the "sign" of the polynomial function. Relatedly, the circuit has a "depth" corresponding to the number of gates of the longest path from the input to the output of the circuit.
In a recent research report (K. Y. Siu and J. Bruck, "On the Dynamic Range of Linear Threshold Elements", IBM Research Report RJ 7237, January 1990), it was proved that it is possible to implement both the logical COMPARISON and ARITHMETIC addition functions in threshold circuits of depth two using majority gates. However, only the existence of the possibility was proved, with the explicit constructions of these circuits left as an open problem.
The challenge of reducing explicit constructions of the COMPARISON and ADDITION functions in depth two majority gate circuits which are described by polynomials using Boolean variables is the necessity to use exponentially large weights. This is because a polynomial used to describe the construction of such a circuit can take on widely varying values, depending upon the number of variables in the polynomial and the values to which the variables may be set by the input bits.